package com.dy.分类.链表.反转链表;
/*
反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
 */

import com.dy.分类.链表.ListNode;

public class Solution {


    //递归
    public static ListNode reverseList3(ListNode head) {
        if (head == null) return null;
        if (head.next == null) {
            return head;
        }
        ListNode t = reverseList3(head.next);
        head.next.next = head;
        head.next = null;

        return t;
    }

    public static ListNode reverseList2(ListNode head) {
        ListNode last = null;
        ListNode next = head;
        while (next != null) {
            next = head.next;
            head.next = last;
            last = head;
            head = next;
        }
        return last;
    }


    public static void main(String[] args) {
        ListNode test = new ListNode(1);
        test.next = new ListNode(2);
        test.next.next = new ListNode(3);
        test.next.next.next = new ListNode(4);
        reverseList3(test);
    }
}
